package com.instant;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int greaterCount(List<Integer> arr , int flag){
        int len = arr.size();
        int count = 0;
        for(int i = 0; i < len ; i++){
            if(arr.get(i) > flag){
                count++;
            }
        }
        return count;
    }

    public int[] resultArray(int[] nums) {
        int len = nums.length;
        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>();
        arr1.add(nums[0]);
        arr2.add(nums[1]);
        int flag = 0;
        for(int i = 2 ; i < len ; i++){
            if(flag != 0 && nums[i] < nums[i - 1]){
                if(flag == 1){
                    arr1.add(nums[i]);
                }else{
                    arr2.add(nums[i]);
                }
                continue;
            }
            int a = greaterCount(arr1 , nums[i]);
            int b = greaterCount(arr2 , nums[i]);
            if(a > b){
                arr1.add(nums[i]);
                flag = 1;
            }else if(b > a){
                arr2.add(nums[i]);
                flag = 2;
            }else{
                flag = 0;
                if(arr1.size() > arr2.size()){
                    arr2.add(nums[i]);
                }else if(arr2.size() > arr1.size()){
                    arr1.add(nums[i]);
                }else{
                    arr1.add(nums[i]);
                }
            }

        }
        int[] result = new int[len];
        for(int i = 0 ; i < arr1.size() ; i++){
            result[i] = arr1.get(i);
        }
        int len1 = arr1.size();
        for(int i = len1 ; i < len ; i++){
            result[ i] = arr2.get(i - len1);
        }
        return result;

    }
}


